package cxydmmszl.chapter09.t156;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;

/**
 * <li style="color: red;">Prob</li>
 * 设计 LRU 缓存结构
 * <li style="color: green;">Desc</li>
 * 设计 LRU 缓存结构，该结构在构造时确定大小，假设大小为 K，并有如下两个功能：<br/>
 * set(key, value)：将记录 (key, value) 插入该结构<br/>
 * get(key)：返回 key 对应的 value 值
 * <br/><br/>[要求]<br/>
 * set 和 get 方法的时间复杂度为 O(1)<br/>
 * 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。<br/>
 * 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
 * <br/><br/>备注：<br/>
 * 1⩽K⩽N⩽10^5<br/>
 * −2∗10^9⩽x,y⩽2∗10^9
 * <li style="color: green;">Input</li>
 * 第一行两个个整数N, K，表示操作数量以及缓存结构大小<br/>
 * 接下来N行，第一行一个整数opt表示操作类型。<br/>
 * 若opt=1，接下来两个整数x, y，表示set(x, y)<br/>
 * 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1<br/>
 * <li style="color: green;">Output</li>
 * 对于每个操作 2，输出一个答案
 * <li style="color: blue;">Link</li> CD64
 *
 * @author habitplus
 * @since 2021-10-31 22:53
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException("Input is invalid!");
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int k = nextInt();

        LRUCache<Integer, Integer> cache = new LRUCache<>(k);
        StringBuilder sb = new StringBuilder();
        int opt, x, y;
        while (n-- > 0) {
            opt = nextInt();
            if (opt == 1) {
                // set
                x = nextInt();
                y = nextInt();
                cache.set(x, y);
            } else {
                // get
                x = nextInt();
                Integer v = cache.get(x);
                sb.append(v == null ? -1 : v).append("\n");
            }
        }
        System.out.print(sb.toString());
    }
}

class Node<V> {
    V val;
    Node<V> next;
    Node<V> prev;

    public Node(V val) {
        this.val = val;
    }
}

class DoubleLinkedList<V> {
    Node<V> head;
    Node<V> tail;

    public DoubleLinkedList() {
        this.head = null;
        this.tail = null;
    }

    /*
        从尾部添加一个节点
     */
    public void add(Node<V> node) {
        if (node == null) return;

        if (this.head == null) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
    }

    /*
        从头部移除一个节点
     */
    public Node<V> poll() {
        if (this.head == null) return null;

        Node<V> cur = this.head;
        if (this.head == this.tail) {
            // 只有一个节点
            this.head = null;
            this.tail = null;
        } else {
            this.head = cur.next;
            cur.next = null;
            this.head.prev = null;
        }
        return cur;
    }

    public void moveNodeToTail(Node<V> node) {
        if (this.tail == node) return;

        if (this.head == node) {
            this.head = node.next;
            this.head.prev = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        node.prev = this.tail;
        node.next = null;
        this.tail.next = node;
        this.tail = node;
    }
}

class LRUCache<K, V> {
    private HashMap<K, Node<V>> keyNodeMap;
    private HashMap<Node<V>, K> nodeKeyMap;
    private DoubleLinkedList<V> nodeList;
    private final int capacity;

    public LRUCache(int capacity) {
        if (capacity < 1) {
            throw new RuntimeException("The capacity must be more than 0 : " + capacity);
        }
        this.capacity = capacity;
        this.keyNodeMap = new HashMap<>();
        this.nodeKeyMap = new HashMap<>();
        this.nodeList = new DoubleLinkedList<>();
    }

    public V get(K key) {
        if (keyNodeMap.containsKey(key)) {
            Node<V> res = this.keyNodeMap.get(key);
            this.nodeList.moveNodeToTail(res);
            return res.val;
        }
        return null;
    }

    public void set(K key, V val) {
        if (this.keyNodeMap.containsKey(key)) {
            // 更新
            Node<V> node = this.keyNodeMap.get(key);
            node.val = val;
            this.nodeList.moveNodeToTail(node);
        } else {
            Node<V> newNode = new Node<>(val);
            this.keyNodeMap.put(key, newNode);
            this.nodeKeyMap.put(newNode, key);
            this.nodeList.add(newNode);
            if (this.keyNodeMap.size() == this.capacity + 1) {
                this.removeMostUnusedCache();
            }
        }
    }

    private void removeMostUnusedCache() {
        Node<V> rNode = this.nodeList.poll();
        K rKey = this.nodeKeyMap.get(rNode);
        this.nodeKeyMap.remove(rNode);
        this.keyNodeMap.remove(rKey);
    }
}
